// xtree internal header
#pragma once
#ifndef _XTREE_
#define _XTREE_
#ifndef RC_INVOKED
#include <xmemory>

#if _HAS_CXX17
#include <xnode_handle.h>
#endif // _HAS_CXX17

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new

_STD_BEGIN
// CLASS TEMPLATE _Tree_unchecked_const_iterator
template <class _Mytree, class _Base = _Iterator_base0>
class _Tree_unchecked_const_iterator : public _Base { // unchecked iterator for nonmutable tree
public:
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mytree::_Nodeptr;
    using value_type      = typename _Mytree::value_type;
    using difference_type = typename _Mytree::difference_type;
    using pointer         = typename _Mytree::const_pointer;
    using reference       = const value_type&;

    _Tree_unchecked_const_iterator() : _Ptr() { // construct with null node pointer
    }

    _Tree_unchecked_const_iterator(_Nodeptr _Pnode, const _Mytree* _Plist)
        : _Ptr(_Pnode) { // construct with node pointer _Pnode
        this->_Adopt(_Plist);
    }

    _NODISCARD reference operator*() const { // return designated value
        return _Ptr->_Myval;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _Tree_unchecked_const_iterator& operator++() { // preincrement
        if (_Ptr->_Right->_Isnil) { // climb looking for right subtree
            _Nodeptr _Pnode;
            while (!(_Pnode = _Ptr->_Parent)->_Isnil && _Ptr == _Pnode->_Right) {
                _Ptr = _Pnode; // ==> parent while right subtree
            }

            _Ptr = _Pnode; // ==> parent (head if end())
        } else {
            _Ptr = _Mytree::_Min(_Ptr->_Right); // ==> smallest of right subtree
        }

        return *this;
    }

    _Tree_unchecked_const_iterator operator++(int) { // postincrement
        _Tree_unchecked_const_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _Tree_unchecked_const_iterator& operator--() { // predecrement
        if (_Ptr->_Isnil) {
            _Ptr = _Ptr->_Right; // end() ==> rightmost
        } else if (_Ptr->_Left->_Isnil) { // climb looking for left subtree
            _Nodeptr _Pnode;
            while (!(_Pnode = _Ptr->_Parent)->_Isnil && _Ptr == _Pnode->_Left) {
                _Ptr = _Pnode; // ==> parent while left subtree
            }

            if (!_Ptr->_Isnil) { // decrement non-begin()
                _Ptr = _Pnode; // ==> parent if not head
            }
        } else {
            _Ptr = _Mytree::_Max(_Ptr->_Left); // ==> largest of left subtree
        }

        return *this;
    }

    _Tree_unchecked_const_iterator operator--(int) { // postdecrement
        _Tree_unchecked_const_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }

    _NODISCARD bool operator==(const _Tree_unchecked_const_iterator& _Right) const { // test for iterator equality
        return _Ptr == _Right._Ptr;
    }

    _NODISCARD bool operator!=(const _Tree_unchecked_const_iterator& _Right) const { // test for iterator inequality
        return !(*this == _Right);
    }

    _Nodeptr _Ptr; // pointer to node
};

// CLASS TEMPLATE _Tree_unchecked_iterator
template <class _Mytree>
class _Tree_unchecked_iterator : public _Tree_unchecked_const_iterator<_Mytree> { // unchecked iterator for mutable tree
public:
    using _Mybase           = _Tree_unchecked_const_iterator<_Mytree>;
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mytree::_Nodeptr;
    using value_type      = typename _Mytree::value_type;
    using difference_type = typename _Mytree::difference_type;
    using pointer         = typename _Mytree::pointer;
    using reference       = value_type&;

    _Tree_unchecked_iterator() { // construct with null node
    }

    _Tree_unchecked_iterator(_Nodeptr _Pnode, const _Mytree* _Plist)
        : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode
    }

    _NODISCARD reference operator*() const { // return designated value
        return (reference) * *(_Mybase*) this;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _Tree_unchecked_iterator& operator++() { // preincrement
        ++static_cast<_Mybase&>(*this);
        return *this;
    }

    _Tree_unchecked_iterator operator++(int) { // postincrement
        _Tree_unchecked_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _Tree_unchecked_iterator& operator--() { // predecrement
        --static_cast<_Mybase&>(*this);
        return *this;
    }

    _Tree_unchecked_iterator operator--(int) { // postdecrement
        _Tree_unchecked_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }
};

// CLASS TEMPLATE _Tree_const_iterator
template <class _Mytree>
class _Tree_const_iterator
    : public _Tree_unchecked_const_iterator<_Mytree, _Iterator_base> { // iterator for nonmutable tree
public:
    using _Mybase           = _Tree_unchecked_const_iterator<_Mytree, _Iterator_base>;
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mytree::_Nodeptr;
    using value_type      = typename _Mytree::value_type;
    using difference_type = typename _Mytree::difference_type;
    using pointer         = typename _Mytree::const_pointer;
    using reference       = const value_type&;

    _Tree_const_iterator() : _Mybase() { // construct with null node pointer
    }

    _Tree_const_iterator(_Nodeptr _Pnode, const _Mytree* _Plist)
        : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode
    }

    _NODISCARD reference operator*() const { // return designated value
#if _ITERATOR_DEBUG_LEVEL != 0
        const auto _Mycont = static_cast<const _Mytree*>(this->_Getcont());
        _STL_ASSERT(_Mycont, "cannot dereference value-initialized map/set iterator");
        _STL_VERIFY(this->_Ptr != _Mycont->_Myhead, "cannot dereference end map/set iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return this->_Ptr->_Myval;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _Tree_const_iterator& operator++() { // preincrement
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(this->_Getcont(), "cannot increment value-initialized map/set iterator");
        _STL_VERIFY(!this->_Ptr->_Isnil, "cannot increment end map/set iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        ++static_cast<_Mybase&>(*this);
        return *this;
    }

    _Tree_const_iterator operator++(int) { // postincrement
        _Tree_const_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _Tree_const_iterator& operator--() { // predecrement
#if _ITERATOR_DEBUG_LEVEL == 0
        --static_cast<_Mybase&>(*this);
#else // ^^^ _ITERATOR_DEBUG_LEVEL == 0 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 0 vvv
        _STL_ASSERT(this->_Getcont(), "cannot decrement value-initialized map/set iterator");
        _Nodeptr _Ptrsav = this->_Ptr;
        --static_cast<_Mybase&>(*this);
        _STL_VERIFY(_Ptrsav != this->_Ptr, "cannot decrement begin map/set iterator");
#endif // _ITERATOR_DEBUG_LEVEL == 0

        return *this;
    }

    _Tree_const_iterator operator--(int) { // postdecrement
        _Tree_const_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }

    _NODISCARD bool operator==(const _Tree_const_iterator& _Right) const { // test for iterator equality
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(this->_Getcont() == _Right._Getcont(), "map/set iterators incompatible");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return this->_Ptr == _Right._Ptr;
    }

    _NODISCARD bool operator!=(const _Tree_const_iterator& _Right) const { // test for iterator inequality
        return !(*this == _Right);
    }

#if _ITERATOR_DEBUG_LEVEL != 0
    friend void _Verify_range(const _Tree_const_iterator& _First, const _Tree_const_iterator& _Last) {
        _STL_VERIFY(_First._Getcont() == _Last._Getcont(), "map/set iterators in range are from different containers");
    }
#endif // _ITERATOR_DEBUG_LEVEL != 0

    using _Prevent_inheriting_unwrap = _Tree_const_iterator;

    _NODISCARD _Tree_unchecked_const_iterator<_Mytree> _Unwrapped() const {
        return _Tree_unchecked_const_iterator<_Mytree>(this->_Ptr, static_cast<const _Mytree*>(this->_Getcont()));
    }

    void _Seek_to(const _Tree_unchecked_const_iterator<_Mytree> _It) {
        this->_Ptr = _It._Ptr;
    }
};

// CLASS TEMPLATE _Tree_iterator
template <class _Mytree>
class _Tree_iterator : public _Tree_const_iterator<_Mytree> { // iterator for mutable tree
public:
    using _Mybase           = _Tree_const_iterator<_Mytree>;
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mytree::_Nodeptr;
    using value_type      = typename _Mytree::value_type;
    using difference_type = typename _Mytree::difference_type;

    using pointer   = typename _Mytree::pointer;
    using reference = value_type&;

    _Tree_iterator() { // construct with null node
    }

    _Tree_iterator(_Nodeptr _Pnode, const _Mytree* _Plist)
        : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode
    }

    _NODISCARD reference operator*() const { // return designated value
        return (reference) * *(_Mybase*) this;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _Tree_iterator& operator++() { // preincrement
        ++static_cast<_Mybase&>(*this);
        return *this;
    }

    _Tree_iterator operator++(int) { // postincrement
        _Tree_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _Tree_iterator& operator--() { // predecrement
        --static_cast<_Mybase&>(*this);
        return *this;
    }

    _Tree_iterator operator--(int) { // postdecrement
        _Tree_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }

    using _Prevent_inheriting_unwrap = _Tree_iterator;

    _NODISCARD _Tree_unchecked_iterator<_Mytree> _Unwrapped() const {
        return _Tree_unchecked_iterator<_Mytree>(this->_Ptr, static_cast<const _Mytree*>(this->_Getcont()));
    }
};

// tree TYPE WRAPPERS
template <class _Value_type, class _Size_type, class _Difference_type, class _Pointer, class _Const_pointer,
    class _Reference, class _Const_reference, class _Nodeptr_type>
struct _Tree_iter_types { // wraps types needed by iterators
    using value_type      = _Value_type;
    using size_type       = _Size_type;
    using difference_type = _Difference_type;
    using pointer         = _Pointer;
    using const_pointer   = _Const_pointer;
    using _Nodeptr        = _Nodeptr_type;
};

template <class _Value_type, class _Voidptr>
struct _Tree_node { // tree node
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _Tree_node>;
    using value_type = _Value_type;
    _Nodeptr _Left; // left subtree, or smallest element if head
    _Nodeptr _Parent; // parent, or root of tree if head
    _Nodeptr _Right; // right subtree, or largest element if head
    char _Color; // _Red or _Black, _Black if head
    char _Isnil; // true only if head (also nil) node
    value_type _Myval; // the stored value, unused if head

    enum _Redbl { // colors for link to parent
        _Red,
        _Black
    };

    _Tree_node(const _Tree_node&) = delete;
    _Tree_node& operator=(const _Tree_node&) = delete;

    template <class _Alloc>
    static _Nodeptr _Buyheadnode(_Alloc& _Al) {
        // allocate a head node, assumes construction of pointer does not throw
        static_assert(is_same_v<typename _Alloc::value_type, _Tree_node>, "Bad _Buyheadnode call");
        using _Alnode_traits = allocator_traits<_Alloc>;
        auto _Pnode          = _Al.allocate(1);
        _Alnode_traits::construct(_Al, _STD addressof(_Pnode->_Left), _Pnode);
        _Alnode_traits::construct(_Al, _STD addressof(_Pnode->_Parent), _Pnode);
        _Alnode_traits::construct(_Al, _STD addressof(_Pnode->_Right), _Pnode);
        _Pnode->_Color = _Black;
        _Pnode->_Isnil = true;
        return _Pnode;
    }

    template <class _Alloc, class... _Valty>
    static _Nodeptr _Buynode(_Alloc& _Al, _Nodeptr _Myhead, _Valty&&... _Val) {
        // allocate a node with defaults and set links and value
        static_assert(is_same_v<typename _Alloc::value_type, _Tree_node>, "Bad _Buynode call");
        using _Alnode_traits = allocator_traits<_Alloc>;
        _Alloc_construct_ptr<_Alloc> _Newnode(_Al);
        _Newnode._Allocate();
        _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Myval), _STD forward<_Valty>(_Val)...);
        // we assume construction of pointers does not throw
        _Alnode_traits::construct(_Newnode._Al, _STD addressof(_Newnode._Ptr->_Left), _Myhead);
        _Alnode_traits::construct(_Newnode._Al, _STD addressof(_Newnode._Ptr->_Parent), _Myhead);
        _Alnode_traits::construct(_Newnode._Al, _STD addressof(_Newnode._Ptr->_Right), _Myhead);
        _Newnode._Ptr->_Color = _Red;
        _Newnode._Ptr->_Isnil = false;
        return _Newnode._Release();
    }

    template <class _Alloc>
    static void _Freenode0(_Alloc& _Al, _Nodeptr _Ptr) noexcept {
        static_assert(is_same_v<typename _Alloc::value_type, _Tree_node>, "Bad _Freenode0 call");
        using _Alnode_traits = allocator_traits<_Alloc>;
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Left));
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Parent));
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Right));
        _Alnode_traits::deallocate(_Al, _Ptr, 1);
    }

    template <class _Alloc>
    static void _Freenode(_Alloc& _Al, _Nodeptr _Ptr) noexcept {
        static_assert(is_same_v<typename _Alloc::value_type, _Tree_node>, "Bad _Freenode call");
        using _Alnode_traits = allocator_traits<_Alloc>;
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Myval));
        _Freenode0(_Al, _Ptr);
    }
};

template <class _Ty>
struct _Tree_simple_types : public _Simple_types<_Ty> { // wraps types needed by iterators
    using _Node    = _Tree_node<_Ty, void*>;
    using _Nodeptr = _Node*;
};

// CLASS TEMPLATE _Tree_val
template <class _Val_types>
class _Tree_val : public _Container_base { // base class for tree to hold data
public:
    using _Nodeptr = typename _Val_types::_Nodeptr;

    using value_type      = typename _Val_types::value_type;
    using size_type       = typename _Val_types::size_type;
    using difference_type = typename _Val_types::difference_type;
    using pointer         = typename _Val_types::pointer;
    using const_pointer   = typename _Val_types::const_pointer;
    using reference       = value_type&;
    using const_reference = const value_type&;

    using _Unchecked_const_iterator = _Tree_unchecked_const_iterator<_Tree_val>;
    using const_iterator            = _Tree_const_iterator<_Tree_val>;

    _Tree_val() : _Myhead(), _Mysize(0) { // initialize data
    }

    enum _Redbl { // colors for link to parent
        _Red,
        _Black
    };

    static _Nodeptr _Max(_Nodeptr _Pnode) { // return rightmost node in subtree at _Pnode
        while (!_Pnode->_Right->_Isnil) {
            _Pnode = _Pnode->_Right;
        }

        return _Pnode;
    }

    static _Nodeptr _Min(_Nodeptr _Pnode) { // return leftmost node in subtree at _Pnode
        while (!_Pnode->_Left->_Isnil) {
            _Pnode = _Pnode->_Left;
        }

        return _Pnode;
    }

    _Nodeptr& _Root() const { // return root of nonmutable tree
        return _Myhead->_Parent;
    }

    _Nodeptr& _Lmost() const { // return leftmost node in nonmutable tree
        return _Myhead->_Left;
    }

    _Nodeptr& _Rmost() const { // return rightmost node in nonmutable tree
        return _Myhead->_Right;
    }

    void _Lrotate(_Nodeptr _Wherenode) { // promote right node to root of subtree
        _Nodeptr _Pnode    = _Wherenode->_Right;
        _Wherenode->_Right = _Pnode->_Left;

        if (!_Pnode->_Left->_Isnil) {
            _Pnode->_Left->_Parent = _Wherenode;
        }

        _Pnode->_Parent = _Wherenode->_Parent;

        if (_Wherenode == _Myhead->_Parent) {
            _Myhead->_Parent = _Pnode;
        } else if (_Wherenode == _Wherenode->_Parent->_Left) {
            _Wherenode->_Parent->_Left = _Pnode;
        } else {
            _Wherenode->_Parent->_Right = _Pnode;
        }

        _Pnode->_Left       = _Wherenode;
        _Wherenode->_Parent = _Pnode;
    }

    void _Rrotate(_Nodeptr _Wherenode) { // promote left node to root of subtree
        _Nodeptr _Pnode   = _Wherenode->_Left;
        _Wherenode->_Left = _Pnode->_Right;

        if (!_Pnode->_Right->_Isnil) {
            _Pnode->_Right->_Parent = _Wherenode;
        }

        _Pnode->_Parent = _Wherenode->_Parent;

        if (_Wherenode == _Myhead->_Parent) {
            _Myhead->_Parent = _Pnode;
        } else if (_Wherenode == _Wherenode->_Parent->_Right) {
            _Wherenode->_Parent->_Right = _Pnode;
        } else {
            _Wherenode->_Parent->_Left = _Pnode;
        }

        _Pnode->_Right      = _Wherenode;
        _Wherenode->_Parent = _Pnode;
    }

    _Nodeptr _Extract(_Unchecked_const_iterator _Where) { // extract node at _Where
        _Nodeptr _Erasednode = _Where._Ptr; // node to erase
        ++_Where; // save successor iterator for return

        _Nodeptr _Fixnode; // the node to recolor as needed
        _Nodeptr _Fixnodeparent; // parent of _Fixnode (which may be nil)
        _Nodeptr _Pnode = _Erasednode;

        if (_Pnode->_Left->_Isnil) {
            _Fixnode = _Pnode->_Right; // stitch up right subtree
        } else if (_Pnode->_Right->_Isnil) {
            _Fixnode = _Pnode->_Left; // stitch up left subtree
        } else { // two subtrees, must lift successor node to replace erased
            _Pnode   = _Where._Ptr; // _Pnode is successor node
            _Fixnode = _Pnode->_Right; // _Fixnode is only subtree
        }

        if (_Pnode == _Erasednode) { // at most one subtree, relink it
            _Fixnodeparent = _Erasednode->_Parent;
            if (!_Fixnode->_Isnil) {
                _Fixnode->_Parent = _Fixnodeparent; // link up
            }

            if (_Root() == _Erasednode) {
                _Root() = _Fixnode; // link down from root
            } else if (_Fixnodeparent->_Left == _Erasednode) {
                _Fixnodeparent->_Left = _Fixnode; // link down to left
            } else {
                _Fixnodeparent->_Right = _Fixnode; // link down to right
            }

            if (_Lmost() == _Erasednode) {
                _Lmost() = _Fixnode->_Isnil ? _Fixnodeparent // smallest is parent of erased node
                                            : _Min(_Fixnode); // smallest in relinked subtree
            }

            if (_Rmost() == _Erasednode) {
                _Rmost() = _Fixnode->_Isnil ? _Fixnodeparent // largest is parent of erased node
                                            : _Max(_Fixnode); // largest in relinked subtree
            }
        } else { // erased has two subtrees, _Pnode is successor to erased
            _Erasednode->_Left->_Parent = _Pnode; // link left up
            _Pnode->_Left               = _Erasednode->_Left; // link successor down

            if (_Pnode == _Erasednode->_Right) {
                _Fixnodeparent = _Pnode; // successor is next to erased
            } else { // successor further down, link in place of erased
                _Fixnodeparent = _Pnode->_Parent; // parent is successor's
                if (!_Fixnode->_Isnil) {
                    _Fixnode->_Parent = _Fixnodeparent; // link fix up
                }

                _Fixnodeparent->_Left        = _Fixnode; // link fix down
                _Pnode->_Right               = _Erasednode->_Right; // link next down
                _Erasednode->_Right->_Parent = _Pnode; // right up
            }

            if (_Root() == _Erasednode) {
                _Root() = _Pnode; // link down from root
            } else if (_Erasednode->_Parent->_Left == _Erasednode) {
                _Erasednode->_Parent->_Left = _Pnode; // link down to left
            } else {
                _Erasednode->_Parent->_Right = _Pnode; // link down to right
            }

            _Pnode->_Parent = _Erasednode->_Parent; // link successor up
            _STD swap(_Pnode->_Color, _Erasednode->_Color); // recolor it
        }

        if (_Erasednode->_Color == _Black) { // erasing black link, must recolor/rebalance tree
            for (; _Fixnode != _Root() && _Fixnode->_Color == _Black; _Fixnodeparent = _Fixnode->_Parent) {
                if (_Fixnode == _Fixnodeparent->_Left) { // fixup left subtree
                    _Pnode = _Fixnodeparent->_Right;
                    if (_Pnode->_Color == _Red) { // rotate red up from right subtree
                        _Pnode->_Color         = _Black;
                        _Fixnodeparent->_Color = _Red;
                        _Lrotate(_Fixnodeparent);
                        _Pnode = _Fixnodeparent->_Right;
                    }

                    if (_Pnode->_Isnil) {
                        _Fixnode = _Fixnodeparent; // shouldn't happen
                    } else if (_Pnode->_Left->_Color == _Black
                               && _Pnode->_Right->_Color == _Black) { // redden right subtree with black children
                        _Pnode->_Color = _Red;
                        _Fixnode       = _Fixnodeparent;
                    } else { // must rearrange right subtree
                        if (_Pnode->_Right->_Color == _Black) { // rotate red up from left sub-subtree
                            _Pnode->_Left->_Color = _Black;
                            _Pnode->_Color        = _Red;
                            _Rrotate(_Pnode);
                            _Pnode = _Fixnodeparent->_Right;
                        }

                        _Pnode->_Color         = _Fixnodeparent->_Color;
                        _Fixnodeparent->_Color = _Black;
                        _Pnode->_Right->_Color = _Black;
                        _Lrotate(_Fixnodeparent);
                        break; // tree now recolored/rebalanced
                    }
                } else { // fixup right subtree
                    _Pnode = _Fixnodeparent->_Left;
                    if (_Pnode->_Color == _Red) { // rotate red up from left subtree
                        _Pnode->_Color         = _Black;
                        _Fixnodeparent->_Color = _Red;
                        _Rrotate(_Fixnodeparent);
                        _Pnode = _Fixnodeparent->_Left;
                    }

                    if (_Pnode->_Isnil) {
                        _Fixnode = _Fixnodeparent; // shouldn't happen
                    } else if (_Pnode->_Right->_Color == _Black
                               && _Pnode->_Left->_Color == _Black) { // redden left subtree with black children
                        _Pnode->_Color = _Red;
                        _Fixnode       = _Fixnodeparent;
                    } else { // must rearrange left subtree
                        if (_Pnode->_Left->_Color == _Black) { // rotate red up from right sub-subtree
                            _Pnode->_Right->_Color = _Black;
                            _Pnode->_Color         = _Red;
                            _Lrotate(_Pnode);
                            _Pnode = _Fixnodeparent->_Left;
                        }

                        _Pnode->_Color         = _Fixnodeparent->_Color;
                        _Fixnodeparent->_Color = _Black;
                        _Pnode->_Left->_Color  = _Black;
                        _Rrotate(_Fixnodeparent);
                        break; // tree now recolored/rebalanced
                    }
                }
            }

            _Fixnode->_Color = _Black; // stopping node is black
        }

        if (0 < _Mysize) {
            --_Mysize;
        }

        return _Erasednode;
    }

    void _Orphan_ptr(const _Nodeptr _Ptr) { // orphan iterators with specified node pointers
#if _ITERATOR_DEBUG_LEVEL == 2
        _Lockit _Lock(_LOCK_DEBUG);
        _Iterator_base12** _Pnext = &this->_Myproxy->_Myfirstiter;
        while (*_Pnext != nullptr) {
            const auto _Pnextptr = static_cast<const_iterator&>(**_Pnext)._Ptr;
            if (_Pnextptr == _Myhead || (_Ptr != nullptr && _Pnextptr != _Ptr)) {
                _Pnext = &(*_Pnext)->_Mynextiter;
            } else { // orphan the iterator
                (*_Pnext)->_Myproxy = nullptr;
                *_Pnext             = (*_Pnext)->_Mynextiter;
            }
        }
#else // ^^^ _ITERATOR_DEBUG_LEVEL == 2 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 2 vvv
        (void) _Ptr;
#endif // _ITERATOR_DEBUG_LEVEL == 2
    }

    template <class _Alnode>
    void _Erase_tree_and_orphan(_Alnode& _Al, _Nodeptr _Rootnode) noexcept {
        // delete a _Tree subtree and orphan nodes
        while (!_Rootnode->_Isnil) { // free subtrees, then node
            _Erase_tree_and_orphan(_Al, _Rootnode->_Right);
            auto _To_delete = _STD exchange(_Rootnode, _Rootnode->_Left);
            _Orphan_ptr(_To_delete);
            _Alnode::value_type::_Freenode(_Al, _To_delete);
        }
    }

    template <class _Alnode>
    void _Erase_tree(_Alnode& _Al, _Nodeptr _Rootnode) noexcept {
        // delete a _Tree subtree
        while (!_Rootnode->_Isnil) { // free subtrees, then node
            _Erase_tree(_Al, _Rootnode->_Right);
            _Alnode::value_type::_Freenode(_Al, _STD exchange(_Rootnode, _Rootnode->_Left));
        }
    }

    template <class _Alnode>
    void _Erase_head(_Alnode& _Al) noexcept { // delete a _Tree head node and subtree
        this->_Orphan_all();
        _Erase_tree(_Al, _Myhead->_Parent);
        _Alnode::value_type::_Freenode0(_Al, _Myhead);
    }

    _Nodeptr _Myhead; // pointer to head node
    size_type _Mysize; // number of elements
};

// STRUCT TEMPLATE _Tree_node_scoped_ptr
template <class _Alnode, class _Scary_val>
struct _Tree_node_scoped_ptr { // temporary storage for allocated node pointers to ensure exception safety
    _Alnode& _Al;
    _Scary_val* _Mycont;

    _Tree_node_scoped_ptr(_Alnode& _Al_, _Scary_val& _Mycont_) : _Al(_Al_), _Mycont(_STD addressof(_Mycont_)) {
        _Mycont->_Myhead = _Alnode::value_type::_Buyheadnode(_Al);
    }

    void _Release() noexcept {
        _Mycont = nullptr;
    }

    ~_Tree_node_scoped_ptr() {
        if (_Mycont) {
            _Mycont->_Erase_head(_Al);
        }
    }
};

// CLASS TEMPLATE _Tree
template <class _Traits>
class _Tree { // ordered red-black tree for map/multimap/set/multiset
public:
    using value_type     = typename _Traits::value_type;
    using allocator_type = typename _Traits::allocator_type;

protected:
    using _Alty          = _Rebind_alloc_t<allocator_type, value_type>;
    using _Alty_traits   = allocator_traits<_Alty>;
    using _Node          = _Tree_node<value_type, typename _Alty_traits::void_pointer>;
    using _Alnode        = _Rebind_alloc_t<allocator_type, _Node>;
    using _Alnode_traits = allocator_traits<_Alnode>;
    using _Nodeptr       = typename _Alnode_traits::pointer;

    using _Scary_val = _Tree_val<conditional_t<_Is_simple_alloc_v<_Alnode>, _Tree_simple_types<value_type>,
        _Tree_iter_types<value_type, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
            typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, value_type&, const value_type&,
            _Nodeptr>>>;

    static constexpr bool _Multi = _Traits::_Multi;

    enum _Redbl { // colors for link to parent
        _Red,
        _Black
    };

public:
    using key_type      = typename _Traits::key_type;
    using value_compare = typename _Traits::value_compare;

    using key_compare = typename _Traits::key_compare;

    using size_type       = typename _Alty_traits::size_type;
    using difference_type = typename _Alty_traits::difference_type;
    using pointer         = typename _Alty_traits::pointer;
    using const_pointer   = typename _Alty_traits::const_pointer;
    using reference       = value_type&;
    using const_reference = const value_type&;

    using iterator =
        conditional_t<is_same_v<key_type, value_type>, _Tree_const_iterator<_Scary_val>, _Tree_iterator<_Scary_val>>;
    using const_iterator            = _Tree_const_iterator<_Scary_val>;
    using _Unchecked_iterator       = conditional_t<is_same_v<key_type, value_type>,
        _Tree_unchecked_const_iterator<_Scary_val>, _Tree_unchecked_iterator<_Scary_val>>;
    using _Unchecked_const_iterator = _Tree_unchecked_const_iterator<_Scary_val>;

    using reverse_iterator       = _STD reverse_iterator<iterator>;
    using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

    using _Pairib = pair<iterator, bool>;
    using _Pairii = pair<iterator, iterator>;
    using _Paircc = pair<const_iterator, const_iterator>;

    struct _Copy_tag { // signals copying
    };
    struct _Move_tag { // signals moving
    };

    _Tree(const key_compare& _Parg) : _Mypair(_One_then_variadic_args_t(), _Parg, _Zero_then_variadic_args_t()) {
        // construct empty tree from comparator
        _Alloc_sentinel_and_proxy();
    }

    _Tree(const key_compare& _Parg, const allocator_type& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Parg, _One_then_variadic_args_t(), _Al) {
        // construct empty tree from comparator, allocator
        _Alloc_sentinel_and_proxy();
    }

    template <class _Any_alloc>
    _Tree(const _Tree& _Right, _Any_alloc&& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Right.key_comp(), _One_then_variadic_args_t(),
              _STD forward<_Any_alloc>(_Al)) {
        // construct tree by copying _Right, allocator
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _Get_data());
        _Tree_node_scoped_ptr<_Alnode, _Scary_val> _Sentinel(_Getal(), _Get_data());
        _Copy(_Right, _Copy_tag());
        _Sentinel._Release();
        _Proxy._Release();
    }

    _Tree(_Tree&& _Right)
        : _Mypair(
              _One_then_variadic_args_t(), _Right.key_comp(), _One_then_variadic_args_t(), _STD move(_Right._Getal())) {
        // construct tree by moving _Right
        _Alloc_sentinel_and_proxy();
        _Swap_val(_Right);
    }

private:
    void _Different_allocator_move_construct(_Tree&& _Right) {
        // TRANSITION, VSO#675959 (inline into only caller when that is fixed)
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _Get_data());
        _Tree_node_scoped_ptr<_Alnode, _Scary_val> _Sentinel(_Getal(), _Get_data());
        _Copy(_Right, _Move_tag());
        _Sentinel._Release();
        _Proxy._Release();
    }

public:
    _Tree(_Tree&& _Right, const allocator_type& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Right.key_comp(), _One_then_variadic_args_t(), _Al) {
        // construct tree by moving _Right, allocator
        if
            _CONSTEXPR_IF(!_Alnode_traits::is_always_equal::value) {
                if (_Getal() != _Right._Getal()) {
                    _Different_allocator_move_construct(_STD move(_Right));
                    return;
                }
            }

        _Alloc_sentinel_and_proxy();
        _Swap_val(_Right);
    }

private:
    void _Move_assign(_Tree& _Right, _Equal_allocators) _NOEXCEPT_COND(is_nothrow_move_assignable_v<key_compare>) {
        clear();
        _Getcomp() = _Right._Getcomp();
        _Pocma(_Getal(), _Right._Getal());
        _Swap_val(_Right);
    }

    void _Move_assign(_Tree& _Right, _Propagate_allocators) {
        if (_Getal() == _Right._Getal()) {
            _Move_assign(_Right, _Equal_allocators{});
        } else {
            clear();
            _Getcomp()            = _Right._Getcomp();
            auto&& _Alproxy       = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
            auto&& _Alproxy_right = _GET_PROXY_ALLOCATOR(_Alnode, _Right._Getal());
            _Container_proxy_ptr<_Alty> _Proxy(_Alproxy_right, _Leave_proxy_unbound{});
            auto& _My_data      = _Get_data();
            auto& _Right_data   = _Right._Get_data();
            const auto _Newhead = _STD exchange(_Right_data._Myhead, _Node::_Buyheadnode(_Right._Getal()));
            const auto _Newsize = _STD exchange(_Right_data._Mysize, size_type{0});
            _My_data._Erase_head(_Getal());
            _Pocma(_Getal(), _Right._Getal());
            _My_data._Myhead = _Newhead;
            _My_data._Mysize = _Newsize;
            _Proxy._Bind(_Alproxy, _STD addressof(_My_data));
            _My_data._Swap_proxy_and_iterators(_Right_data);
        }
    }

    void _Move_assign(_Tree& _Right, _No_propagate_allocators) {
        if (_Getal() == _Right._Getal()) {
            _Move_assign(_Right, _Equal_allocators{});
        } else {
            clear();
            _Getcomp() = _Right._Getcomp();
            _Copy(_Right, _Move_tag());
        }
    }

public:
    _Tree& operator=(_Tree&& _Right) _NOEXCEPT_COND(noexcept(_Move_assign(_Right, _Choose_pocma<_Alnode>{}))) {
        if (this != _STD addressof(_Right)) { // different, move it
            _Move_assign(_Right, _Choose_pocma<_Alnode>{});
        }

        return *this;
    }

private:
    void _Swap_val(_Tree& _Right) { // swap contents with _Right, equal allocators
        auto& _My_data    = _Get_data();
        auto& _Right_data = _Right._Get_data();
        _My_data._Swap_proxy_and_iterators(_Right_data);
        _Swap_adl(_Getcomp(), _Right._Getcomp());
        _Swap_adl(_My_data._Myhead, _Right_data._Myhead);
        _STD swap(_My_data._Mysize, _Right_data._Mysize);
    }

public:
    template <class... _Valty>
    _Pairib emplace(_Valty&&... _Val) { // try to insert value_type(_Val...), favoring right side
        _Nodeptr _Newnode = _Buynode(_STD forward<_Valty>(_Val)...);
        auto _Result      = _Insert_nohint(false, _Newnode->_Myval, _Newnode);
        return {iterator(_Result.first, _STD addressof(_Get_data())), _Result.second};
    }

    template <class... _Valty>
    iterator emplace_hint(const_iterator _Where, _Valty&&... _Val) { // insert value_type(_Val...) at _Where
        _Nodeptr _Newnode       = _Buynode(_STD forward<_Valty>(_Val)...);
        const auto _My_data_ptr = _STD addressof(_Get_data());
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _My_data_ptr, "map/set insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        return iterator(_Insert_hint(_Where._Unwrapped(), _Newnode->_Myval, _Newnode), _My_data_ptr);
    }

    ~_Tree() noexcept { // destroy tree
        _Get_data()._Erase_head(_Getal());
#if _ITERATOR_DEBUG_LEVEL != 0
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Delete_plain(_Alproxy, _Get_data()._Myproxy);
#endif /* _ITERATOR_DEBUG_LEVEL != 0 */
    }

private:
    void _Copy_assign(const _Tree& _Right, false_type) {
        clear();
        _Getcomp() = _Right._Getcomp();
        _Pocca(_Getal(), _Right._Getal());
        _Copy(_Right, _Copy_tag());
    }

    void _Copy_assign(const _Tree& _Right, true_type) {
        if (_Getal() == _Right._Getal()) {
            _Copy_assign(_Right, false_type{});
        } else {
            clear();
            _Get_data()._Orphan_all();
            auto&& _Alproxy       = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
            auto&& _Alproxy_right = _GET_PROXY_ALLOCATOR(_Alnode, _Right._Getal());
            _Container_proxy_ptr<_Alty> _Proxy(_Alproxy_right, _Leave_proxy_unbound{});
            auto& _Nc_right = const_cast<_Tree&>(_Right);
            auto& _My_data  = _Get_data();
            auto _Newhead   = _Node::_Buyheadnode(_Nc_right._Getal());
            _Node::_Freenode0(_Getal(), _My_data._Myhead);
            _Pocca(_Getal(), _Right._Getal());
            _My_data._Myhead = _Newhead;
            _Proxy._Bind(_Alproxy, _STD addressof(_My_data));
            _Getcomp() = _Right._Getcomp();
            _Copy(_Right, _Copy_tag());
        }
    }

public:
    _Tree& operator=(const _Tree& _Right) {
        if (this != _STD addressof(_Right)) { // different, assign it
            _Copy_assign(_Right, _Choose_pocca<_Alnode>{});
        }

        return *this;
    }

    _NODISCARD iterator begin() noexcept { // return iterator for beginning of mutable sequence
        auto& _My_data = _Get_data();
        return iterator(_My_data._Lmost(), _STD addressof(_My_data));
    }

    _NODISCARD const_iterator begin() const noexcept { // return iterator for beginning of nonmutable sequence
        auto& _My_data = _Get_data();
        return const_iterator(_My_data._Lmost(), _STD addressof(_My_data));
    }

    _NODISCARD iterator end() noexcept { // return iterator for end of mutable sequence
        auto& _My_data = _Get_data();
        return iterator(_My_data._Myhead, _STD addressof(_My_data));
    }

    _NODISCARD const_iterator end() const noexcept { // return iterator for end of nonmutable sequence
        auto& _My_data = _Get_data();
        return const_iterator(_My_data._Myhead, _STD addressof(_My_data));
    }

    _Unchecked_iterator _Unchecked_begin() noexcept { // return unchecked iterator for beginning of mutable sequence
        return _Unchecked_iterator(_Get_data()._Lmost(), nullptr);
    }

    _Unchecked_const_iterator _Unchecked_begin() const noexcept {
        // return unchecked iterator for beginning of nonmutable sequence
        return _Unchecked_const_iterator(_Get_data()._Lmost(), nullptr);
    }

    _Unchecked_iterator _Unchecked_end() noexcept { // return unchecked iterator for end of mutable sequence
        return _Unchecked_iterator(_Get_data()._Myhead, nullptr);
    }

    _Unchecked_const_iterator _Unchecked_end() const noexcept {
        // return unchecked iterator for end of nonmutable sequence
        return _Unchecked_const_iterator(_Get_data()._Myhead, nullptr);
    }

    _NODISCARD reverse_iterator rbegin() noexcept { // return iterator for beginning of reversed mutable sequence
        return reverse_iterator(end());
    }

    _NODISCARD const_reverse_iterator rbegin() const
        noexcept { // return iterator for beginning of reversed nonmutable sequence
        return const_reverse_iterator(end());
    }

    _NODISCARD reverse_iterator rend() noexcept { // return iterator for end of reversed mutable sequence
        return reverse_iterator(begin());
    }

    _NODISCARD const_reverse_iterator rend() const noexcept { // return iterator for end of reversed nonmutable sequence
        return const_reverse_iterator(begin());
    }

    _NODISCARD const_iterator cbegin() const noexcept { // return iterator for beginning of nonmutable sequence
        return begin();
    }

    _NODISCARD const_iterator cend() const noexcept { // return iterator for end of nonmutable sequence
        return end();
    }

    _NODISCARD const_reverse_iterator crbegin() const
        noexcept { // return iterator for beginning of reversed nonmutable sequence
        return rbegin();
    }

    _NODISCARD const_reverse_iterator crend() const
        noexcept { // return iterator for end of reversed nonmutable sequence
        return rend();
    }

    _NODISCARD size_type size() const noexcept { // return length of sequence
        return _Get_data()._Mysize;
    }

    _NODISCARD size_type max_size() const noexcept { // return maximum possible length of sequence
        return _Alnode_traits::max_size(_Getal());
    }

    _NODISCARD bool empty() const noexcept { // return true only if sequence is empty
        return size() == 0;
    }

    _NODISCARD allocator_type get_allocator() const noexcept { // return allocator object for values
        return static_cast<allocator_type>(_Getal());
    }

    _NODISCARD key_compare key_comp() const { // return object for comparing keys
        return _Getcomp();
    }

    _NODISCARD value_compare value_comp() const { // return object for comparing values
        return value_compare(key_comp());
    }

    template <bool _Multi2 = _Multi, enable_if_t<!_Multi2, int> = 0>
    _Pairib insert(const value_type& _Val) { // try to insert node with value _Val, favoring right side
        auto _Result = _Insert_nohint(false, _Val, _Not_a_node_tag());
        return {iterator(_Result.first, _STD addressof(_Get_data())), _Result.second};
    }

    template <bool _Multi2 = _Multi, enable_if_t<_Multi2, int> = 0>
    iterator insert(const value_type& _Val) { // try to insert node with value _Val, favoring right side
        return iterator(_Insert_nohint(false, _Val, _Not_a_node_tag()).first, _STD addressof(_Get_data()));
    }

    template <bool _Multi2 = _Multi, enable_if_t<!_Multi2, int> = 0>
    _Pairib insert(value_type&& _Val) { // try to insert node with value _Val, favoring right side
        auto _Result = _Insert_nohint(false, _STD move(_Val), _Not_a_node_tag());
        return {iterator(_Result.first, _STD addressof(_Get_data())), _Result.second};
    }

    template <bool _Multi2 = _Multi, enable_if_t<_Multi2, int> = 0>
    iterator insert(value_type&& _Val) { // try to insert node with value _Val, favoring right side
        return iterator(_Insert_nohint(false, _STD move(_Val), _Not_a_node_tag()).first, _STD addressof(_Get_data()));
    }

    iterator insert(const_iterator _Where, const value_type& _Val) {
        // try to insert node with value _Val using _Where as a hint
        const auto _My_data_ptr = _STD addressof(_Get_data());
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _My_data_ptr, "map/set insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        return iterator(_Insert_hint(_Where._Unwrapped(), _Val, _Not_a_node_tag()), _My_data_ptr);
    }

    iterator insert(const_iterator _Where, value_type&& _Val) {
        // try to insert node with value _Val using _Where as a hint
        const auto _My_data_ptr = _STD addressof(_Get_data());
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _My_data_ptr, "map/set insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        return iterator(_Insert_hint(_Where._Unwrapped(), _STD move(_Val), _Not_a_node_tag()), _My_data_ptr);
    }

    template <class _Iter>
    void insert(_Iter _First, _Iter _Last) { // insert [_First, _Last) one at a time
        _Adl_verify_range(_First, _Last);
        auto _UFirst      = _Get_unwrapped(_First);
        const auto _ULast = _Get_unwrapped(_Last);
        for (; _UFirst != _ULast; ++_UFirst) {
            emplace_hint(end(), *_UFirst);
        }
    }

    void insert(initializer_list<value_type> _Ilist) { // insert initializer_list
        insert(_Ilist.begin(), _Ilist.end());
    }

private:
    _Nodeptr _Erase_unchecked(_Unchecked_const_iterator _Where) {
        auto& _My_data                       = _Get_data();
        _Unchecked_const_iterator _Successor = _Where;
        ++_Successor; // save successor iterator for return
        _Nodeptr _Erasednode = _My_data._Extract(_Where); // node to erase
        _My_data._Orphan_ptr(_Erasednode);
        _Node::_Freenode(_Getal(), _Erasednode); // delete erased node
        return _Successor._Ptr; // return successor nodeptr
    }

    _Nodeptr _Erase_unchecked(_Unchecked_const_iterator _First, _Unchecked_const_iterator _Last) {
        const auto _Begin = _Unchecked_begin();
        if (_First == _Begin && _Last == _Unchecked_end()) {
            // erase all
            clear();
            return _Last._Ptr;
        }

        // partial erase, one at a time
        while (_First != _Last) {
            _Erase_unchecked(_First++);
        }

        return _Last._Ptr;
    }

public:
    template <class _Iter = iterator, class = enable_if_t<!is_same_v<_Iter, const_iterator>>>
    iterator erase(iterator _Where) { // erase element at _Where
        const auto _My_data_ptr = _STD addressof(_Get_data());
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _My_data_ptr, "map/set erase iterator from incorrect container");
        _STL_VERIFY(!_Where._Ptr->_Isnil, "cannot erase map/set end() iterator");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        return iterator(_Erase_unchecked(_Where._Unwrapped()), _My_data_ptr);
    }

    iterator erase(const_iterator _Where) { // erase element at _Where
        const auto _My_data_ptr = _STD addressof(_Get_data());
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _My_data_ptr, "map/set erase iterator from incorrect container");
        _STL_VERIFY(!_Where._Ptr->_Isnil, "cannot erase map/set end() iterator");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        return iterator(_Erase_unchecked(_Where._Unwrapped()), _My_data_ptr);
    }

    iterator erase(const_iterator _First, const_iterator _Last) { // erase [_First, _Last)
        return iterator(_Erase_unchecked(_First._Unwrapped(), _Last._Unwrapped()), _STD addressof(_Get_data()));
    }

    size_type erase(const key_type& _Keyval) { // erase and count all that match _Keyval
        const auto _Where = _Eqrange(_Keyval);
        const _Unchecked_const_iterator _First(_Where.first, nullptr);
        const _Unchecked_const_iterator _Last(_Where.second, nullptr);
        const auto _Num = static_cast<size_type>(_STD distance(_First, _Last));
        _Erase_unchecked(_First, _Last);
        return _Num;
    }

    void clear() noexcept { // erase all
        auto& _My_data = _Get_data();
        _My_data._Orphan_ptr(nullptr);
        auto _Head = _My_data._Myhead;
        _My_data._Erase_tree(_Getal(), _Head->_Parent);
        _Head->_Parent   = _Head;
        _Head->_Left     = _Head;
        _Head->_Right    = _Head;
        _My_data._Mysize = 0;
    }

private:
    template <class _Other>
    _NODISCARD _Nodeptr _Find(const _Other& _Keyval) const {
        const auto _First_not_less = _Lbound(_Keyval);
        const auto _My_head        = _Get_data()._Myhead;
        return _First_not_less == _My_head || _DEBUG_LT_PRED(_Getcomp(), _Keyval, _Key(_First_not_less))
                   ? _My_head
                   : _First_not_less;
    }

public:
    _NODISCARD iterator find(const key_type& _Keyval) {
        // find an element that matches _Keyval
        return iterator(_Find(_Keyval), _STD addressof(_Get_data()));
    }

    _NODISCARD const_iterator find(const key_type& _Keyval) const {
        // find an element that matches _Keyval
        return const_iterator(_Find(_Keyval), _STD addressof(_Get_data()));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD iterator find(const _Other& _Keyval) {
        // find an element that matches _Keyval
        return iterator(_Find(_Keyval), _STD addressof(_Get_data()));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD const_iterator find(const _Other& _Keyval) const {
        // find an element that matches _Keyval
        return const_iterator(_Find(_Keyval), _STD addressof(_Get_data()));
    }

#if _HAS_CXX20
    _NODISCARD bool contains(const key_type& _Keyval) const {
        // check if an element exists that matches _Keyval
        const auto _First_not_less = _Lbound(_Keyval);
        return _First_not_less != _Get_data()._Myhead && !_DEBUG_LT_PRED(_Getcomp(), _Keyval, _Key(_First_not_less));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD bool contains(const _Other& _Keyval) const {
        // check if an element exists that matches _Keyval
        const auto _First_not_less = _Lbound(_Keyval);
        return _First_not_less != _Get_data()._Myhead && !_DEBUG_LT_PRED(_Getcomp(), _Keyval, _Key(_First_not_less));
    }
#endif // _HAS_CXX20

    _NODISCARD size_type count(const key_type& _Keyval) const { // count all elements that match _Keyval
        if
            _CONSTEXPR_IF(_Multi) {
                const auto _Ans = _Eqrange(_Keyval);
                return static_cast<size_type>(_STD distance(
                    _Unchecked_const_iterator(_Ans.first, nullptr), _Unchecked_const_iterator(_Ans.second, nullptr)));
            }
        else {
            const auto _First_not_less = _Lbound(_Keyval);
            return _First_not_less != _Get_data()._Myhead
                   && !_DEBUG_LT_PRED(_Getcomp(), _Keyval, _Key(_First_not_less));
        }
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD size_type count(const _Other& _Keyval) const { // count all elements that match _Keyval
        const auto _Ans = _Eqrange(_Keyval);
        return static_cast<size_type>(_STD distance(
            _Unchecked_const_iterator(_Ans.first, nullptr), _Unchecked_const_iterator(_Ans.second, nullptr)));
    }

    _NODISCARD iterator lower_bound(const key_type& _Keyval) {
        // find leftmost node not less than _Keyval in mutable tree
        return iterator(_Lbound(_Keyval), _STD addressof(_Get_data()));
    }

    _NODISCARD const_iterator lower_bound(const key_type& _Keyval) const {
        // find leftmost node not less than _Keyval in nonmutable tree
        return const_iterator(_Lbound(_Keyval), _STD addressof(_Get_data()));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD iterator lower_bound(const _Other& _Keyval) {
        // find leftmost node not less than _Keyval in mutable tree
        return iterator(_Lbound(_Keyval), _STD addressof(_Get_data()));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD const_iterator lower_bound(const _Other& _Keyval) const {
        // find leftmost node not less than _Keyval in nonmutable tree
        return const_iterator(_Lbound(_Keyval), _STD addressof(_Get_data()));
    }

    _NODISCARD iterator upper_bound(const key_type& _Keyval) {
        // find leftmost node greater than _Keyval in mutable tree
        return iterator(_Ubound(_Keyval), _STD addressof(_Get_data()));
    }

    _NODISCARD const_iterator upper_bound(const key_type& _Keyval) const {
        // find leftmost node greater than _Keyval in nonmutable tree
        return const_iterator(_Ubound(_Keyval), _STD addressof(_Get_data()));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD iterator upper_bound(const _Other& _Keyval) {
        // find leftmost node greater than _Keyval in mutable tree
        return iterator(_Ubound(_Keyval), _STD addressof(_Get_data()));
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD const_iterator upper_bound(const _Other& _Keyval) const {
        // find leftmost node greater than _Keyval in nonmutable tree
        return const_iterator(_Ubound(_Keyval), _STD addressof(_Get_data()));
    }

    _NODISCARD _Pairii equal_range(const key_type& _Keyval) { // find range equivalent to _Keyval
        const auto _Result      = _Eqrange(_Keyval);
        const auto _My_data_ptr = _STD addressof(_Get_data());
        return {iterator(_Result.first, _My_data_ptr), iterator(_Result.second, _My_data_ptr)};
    }

    _NODISCARD _Paircc equal_range(const key_type& _Keyval) const { // find range equivalent to _Keyval
        const auto _Result      = _Eqrange(_Keyval);
        const auto _My_data_ptr = _STD addressof(_Get_data());
        return {const_iterator(_Result.first, _My_data_ptr), const_iterator(_Result.second, _My_data_ptr)};
    }

    template <class _Other, class _Mycomp = key_compare,
        class = typename _Mycomp::is_transparent>
    _NODISCARD _Pairii equal_range(const _Other& _Keyval) { // find range equivalent to _Keyval
        const auto _Result      = _Eqrange(_Keyval);
        const auto _My_data_ptr = _STD addressof(_Get_data());
        return {iterator(_Result.first, _My_data_ptr), iterator(_Result.second, _My_data_ptr)};
    }

    template <class _Other, class _Mycomp = key_compare, class = typename _Mycomp::is_transparent>
    _NODISCARD _Paircc equal_range(const _Other& _Keyval) const { // find range equivalent to _Keyval
        const auto _Result      = _Eqrange(_Keyval);
        const auto _My_data_ptr = _STD addressof(_Get_data());
        return {const_iterator(_Result.first, _My_data_ptr), const_iterator(_Result.second, _My_data_ptr)};
    }

    void swap(_Tree& _Right) _NOEXCEPT_COND(_Is_nothrow_swappable<key_compare>::value) { // strengthened
        // exchange contents with _Right
        if (this != _STD addressof(_Right)) { // (maybe) swap allocators, swap control information
            _Pocs(_Getal(), _Right._Getal());
            _Swap_val(_Right);
        }
    }

protected:
    template <class _Valty>
    _Nodeptr _Buy_if_not_node(_Nodeptr _Node, _Valty&&) { // node exists, just return it
        return _Node;
    }

    template <class _Valty>
    _Nodeptr _Buy_if_not_node(_Not_a_node_tag, _Valty&& _Val) { // node doesn't exist, make it
        return _Buynode(_STD forward<_Valty>(_Val));
    }

    void _Destroy_if_node(_Nodeptr _Newnode) { // node exists, destroy it
        _Node::_Freenode(_Getal(), _Newnode);
    }

    void _Destroy_if_node(_Not_a_node_tag) { // node doesn't exist, do nothing
    }

    template <class _Valty, class _Nodety>
    _Nodeptr _Insert_hint(_Unchecked_const_iterator _Where, _Valty&& _Val, _Nodety _Newnode) {
        // try to insert node using _Where as a hint
        _Unchecked_const_iterator _Next;
        bool _Leftish  = false; // assume nearest point is end of sequence
        auto& _My_data = _Get_data();

        _TRY_BEGIN
        if (size() == 0) {
            return _Insert_at(true, _My_data._Myhead, _STD forward<_Valty>(_Val), _Newnode); // empty tree
        } else if
            _CONSTEXPR_IF(_Multi) { // insert even if duplicate
                if (_Where == _Unchecked_begin()) { // insert at beginning if before first element
                    if (!_DEBUG_LT_PRED(_Getcomp(), _Key(_Where._Ptr), _Kfn(_Val))) {
                        return _Insert_at(true, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                    }

                    _Leftish = true; // nearest point is beginning of sequence
                } else if (_Where == _Unchecked_end()) { // insert at end if after last element
                    if (!_DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val), _Key(_My_data._Rmost()))) {
                        return _Insert_at(false, _My_data._Rmost(), _STD forward<_Valty>(_Val), _Newnode);
                    }
                } else if (!_DEBUG_LT_PRED(_Getcomp(), _Key(_Where._Ptr), _Kfn(_Val))
                           && !_DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val),
                                  _Key((--(_Next = _Where))._Ptr))) { // insert before _Where
                    if (_Next._Ptr->_Right->_Isnil) {
                        return _Insert_at(false, _Next._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                    } else {
                        return _Insert_at(true, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                    }
                } else if (!_DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val), _Key(_Where._Ptr))
                           && (++(_Next = _Where) == _Unchecked_end()
                                  || !_DEBUG_LT_PRED(
                                         _Getcomp(), _Key(_Next._Ptr), _Kfn(_Val)))) { // insert after _Where
                    if (_Where._Ptr->_Right->_Isnil) {
                        return _Insert_at(false, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                    } else {
                        return _Insert_at(true, _Next._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                    }
                } else {
                    _Leftish = true; // nearest point is beginning of sequence
                }
            }
        else { // insert only if unique
            if (_Where == _Unchecked_begin()) { // insert at beginning if before first element
                if (_DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val), _Key(_Where._Ptr))) {
                    return _Insert_at(true, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                }
            } else if (_Where == _Unchecked_end()) { // insert at end if after last element
                if (_DEBUG_LT_PRED(_Getcomp(), _Key(_My_data._Rmost()), _Kfn(_Val))) {
                    return _Insert_at(false, _My_data._Rmost(), _STD forward<_Valty>(_Val), _Newnode);
                }
            } else if (_DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val), _Key(_Where._Ptr))
                       && _DEBUG_LT_PRED(_Getcomp(), _Key((--(_Next = _Where))._Ptr),
                              _Kfn(_Val))) { // insert before _Where
                if (_Next._Ptr->_Right->_Isnil) {
                    return _Insert_at(false, _Next._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                } else {
                    return _Insert_at(true, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                }
            } else if (_DEBUG_LT_PRED(_Getcomp(), _Key(_Where._Ptr), _Kfn(_Val))
                       && (++(_Next = _Where) == _Unchecked_end()
                              || _DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val), _Key(_Next._Ptr)))) { // insert after _Where
                if (_Where._Ptr->_Right->_Isnil) {
                    return _Insert_at(false, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                } else {
                    return _Insert_at(true, _Next._Ptr, _STD forward<_Valty>(_Val), _Newnode);
                }
            }
        }
        _CATCH_ALL
        _Destroy_if_node(_Newnode);
        _RERAISE;
        _CATCH_END

        return _Insert_nohint(_Leftish, _STD forward<_Valty>(_Val), _Newnode).first;
    }

    template <class _Valty, class _Nodety>
    pair<_Nodeptr, bool> _Insert_nohint(bool _Leftish, _Valty&& _Val, _Nodety _Newnode) {
        // try to insert node, on left if _Leftish
        auto& _My_data = _Get_data();
        _TRY_BEGIN
        _Nodeptr _Wherenode = _My_data._Myhead;
        _Nodeptr _Trynode   = _Wherenode->_Parent;
        bool _Addleft       = true; // add to left of head if tree empty

        while (!_Trynode->_Isnil) { // look for leaf to insert before (_Addleft) or after
            _Wherenode = _Trynode;
            if (_Leftish) {
                _Addleft = !_DEBUG_LT_PRED(_Getcomp(), _Key(_Trynode),
                    _Kfn(_Val)); // favor left end
            } else {
                _Addleft = _DEBUG_LT_PRED(_Getcomp(), _Kfn(_Val),
                    _Key(_Trynode)); // favor right end
            }

            _Trynode = _Addleft ? _Trynode->_Left : _Trynode->_Right;
        }

        if
            _CONSTEXPR_IF(_Multi) {
                return {_Insert_at(_Addleft, _Wherenode, _STD forward<_Valty>(_Val), _Newnode), true};
            }
        else { // insert only if unique
            _Unchecked_iterator _Where(_Wherenode, nullptr);
            if (!_Addleft) { // need to test if insert after is okay
            } else if (_Where == _Unchecked_begin()) {
                return {_Insert_at(true, _Where._Ptr, _STD forward<_Valty>(_Val), _Newnode), true};
            } else {
                --_Where; // need to test if insert before is okay
            }

            if (_DEBUG_LT_PRED(_Getcomp(), _Key(_Where._Ptr), _Kfn(_Val))) {
                return {_Insert_at(_Addleft, _Wherenode, _STD forward<_Valty>(_Val), _Newnode), true};
            } else { // duplicate, don't insert
                _Destroy_if_node(_Newnode);
                return {_Where._Ptr, false};
            }
        }
        _CATCH_ALL
        _Destroy_if_node(_Newnode);
        _RERAISE;
        _CATCH_END
    }

    template <class _Valty, class _Nodety>
    _Nodeptr _Insert_at(bool _Addleft, _Nodeptr _Wherenode, _Valty&& _Val, _Nodety _Node) {
        // add node with value next to _Wherenode, to left if _Addleft
        auto& _My_data = _Get_data();
        if (max_size() - 1 <= _My_data._Mysize) { // tree would get too big, fail
            _Destroy_if_node(_Node);
            _Xlength_error("map/set<T> too long");
        }

        _Nodeptr _Newnode = _Buy_if_not_node(_Node, _STD forward<_Valty>(_Val));

        ++_My_data._Mysize;
        _Newnode->_Parent = _Wherenode;

        if (_Wherenode == _My_data._Myhead) { // first node in tree, just set head values
            _My_data._Root()  = _Newnode;
            _My_data._Lmost() = _Newnode;
            _My_data._Rmost() = _Newnode;
        } else if (_Addleft) { // add to left of _Wherenode
            _Wherenode->_Left = _Newnode;
            if (_Wherenode == _My_data._Lmost()) {
                _My_data._Lmost() = _Newnode;
            }
        } else { // add to right of _Wherenode
            _Wherenode->_Right = _Newnode;
            if (_Wherenode == _My_data._Rmost()) {
                _My_data._Rmost() = _Newnode;
            }
        }

        for (_Nodeptr _Pnode = _Newnode; _Pnode->_Parent->_Color == _Red;) {
            if (_Pnode->_Parent == _Pnode->_Parent->_Parent->_Left) { // fixup red-red in left subtree
                _Wherenode = _Pnode->_Parent->_Parent->_Right;
                if (_Wherenode->_Color == _Red) { // parent has two red children, blacken both
                    _Pnode->_Parent->_Color          = _Black;
                    _Wherenode->_Color               = _Black;
                    _Pnode->_Parent->_Parent->_Color = _Red;
                    _Pnode                           = _Pnode->_Parent->_Parent;
                } else { // parent has red and black children
                    if (_Pnode == _Pnode->_Parent->_Right) { // rotate right child to left
                        _Pnode = _Pnode->_Parent;
                        _My_data._Lrotate(_Pnode);
                    }

                    _Pnode->_Parent->_Color          = _Black; // propagate red up
                    _Pnode->_Parent->_Parent->_Color = _Red;
                    _My_data._Rrotate(_Pnode->_Parent->_Parent);
                }
            } else { // fixup red-red in right subtree
                _Wherenode = _Pnode->_Parent->_Parent->_Left;
                if (_Wherenode->_Color == _Red) { // parent has two red children, blacken both
                    _Pnode->_Parent->_Color          = _Black;
                    _Wherenode->_Color               = _Black;
                    _Pnode->_Parent->_Parent->_Color = _Red;
                    _Pnode                           = _Pnode->_Parent->_Parent;
                } else { // parent has red and black children
                    if (_Pnode == _Pnode->_Parent->_Left) { // rotate left child to right
                        _Pnode = _Pnode->_Parent;
                        _My_data._Rrotate(_Pnode);
                    }

                    _Pnode->_Parent->_Color          = _Black; // propagate red up
                    _Pnode->_Parent->_Parent->_Color = _Red;
                    _My_data._Lrotate(_Pnode->_Parent->_Parent);
                }
            }
        }

        _My_data._Root()->_Color = _Black; // root is always black
        return _Newnode;
    }

    template <class _Moveit>
    void _Copy(const _Tree& _Right, _Moveit _Movefl) { // copy or move entire tree from _Right
        auto& _My_data   = _Get_data();
        _My_data._Root() = _Copy_nodes(_Right._Get_data()._Root(), _My_data._Myhead, _Movefl);
        _My_data._Mysize = _Right.size();
        if (!_My_data._Root()->_Isnil) { // nonempty tree, look for new smallest and largest
            _My_data._Lmost() = _Scary_val::_Min(_My_data._Root());
            _My_data._Rmost() = _Scary_val::_Max(_My_data._Root());
        } else { // empty tree, just tidy head pointers
            _My_data._Lmost() = _My_data._Myhead;
            _My_data._Rmost() = _My_data._Myhead;
        }
    }

    template <class _Ty, class _Is_set>
    _Nodeptr _Copy_or_move(_Ty& _Val, _Copy_tag, _Is_set) { // copy to new node
        return _Buynode(_Val);
    }

    template <class _Ty>
    _Nodeptr _Copy_or_move(_Ty& _Val, _Move_tag, true_type) { // move to new node -- set
        return _Buynode(_STD move(_Val));
    }

    template <class _Ty>
    _Nodeptr _Copy_or_move(_Ty& _Val, _Move_tag, false_type) { // move to new node -- map
        return _Buynode(_STD move(const_cast<key_type&>(_Val.first)), _STD move(_Val.second));
    }

    template <class _Moveit>
    _Nodeptr _Copy_nodes(_Nodeptr _Rootnode, _Nodeptr _Wherenode,
        _Moveit _Movefl) { // copy entire subtree, recursively
        _Nodeptr _Newroot = _Get_data()._Myhead; // point at nil node

        if (!_Rootnode->_Isnil) { // copy or move a node, then any subtrees
            typename is_same<key_type, value_type>::type _Is_set;
            _Nodeptr _Pnode = _Copy_or_move(_Rootnode->_Myval, _Movefl, _Is_set);
            _Pnode->_Parent = _Wherenode;
            _Pnode->_Color  = _Rootnode->_Color;
            if (_Newroot->_Isnil) {
                _Newroot = _Pnode; // memorize new root
            }

            _TRY_BEGIN
            _Pnode->_Left  = _Copy_nodes(_Rootnode->_Left, _Pnode, _Movefl);
            _Pnode->_Right = _Copy_nodes(_Rootnode->_Right, _Pnode, _Movefl);
            _CATCH_ALL
            _Get_data()._Erase_tree_and_orphan(_Getal(), _Newroot); // subtree copy failed, bail out
            _RERAISE;
            _CATCH_END
        }

        return _Newroot; // return newly constructed tree
    }

    template <class _Other>
    pair<_Nodeptr, _Nodeptr> _Eqrange(const _Other& _Keyval) const { // find leftmost node not less than _Keyval
        auto& _My_data   = _Get_data();
        _Nodeptr _Pnode  = _My_data._Root();
        _Nodeptr _Lonode = _My_data._Myhead; // end() if search fails
        _Nodeptr _Hinode = _My_data._Myhead; // end() if search fails

        while (!_Pnode->_Isnil) {
            if (_DEBUG_LT_PRED(_Getcomp(), _Key(_Pnode), _Keyval)) {
                _Pnode = _Pnode->_Right; // descend right subtree
            } else { // _Pnode not less than _Keyval, remember it
                if (_Hinode->_Isnil && _DEBUG_LT_PRED(_Getcomp(), _Keyval, _Key(_Pnode))) {
                    _Hinode = _Pnode; // _Pnode greater, remember it
                }

                _Lonode = _Pnode;
                _Pnode  = _Pnode->_Left; // descend left subtree
            }
        }

        _Pnode = _Hinode->_Isnil ? _My_data._Root() : _Hinode->_Left; // continue scan for upper bound
        while (!_Pnode->_Isnil) {
            if (_DEBUG_LT_PRED(_Getcomp(), _Keyval, _Key(_Pnode))) { // _Pnode greater than _Keyval, remember it
                _Hinode = _Pnode;
                _Pnode  = _Pnode->_Left; // descend left subtree
            } else {
                _Pnode = _Pnode->_Right; // descend right subtree
            }
        }

        return {_Lonode, _Hinode};
    }

    bool _Compare(
        const key_type& _Left, const key_type& _Right) const { // compare key_type to key_type, with debug checks
        return _DEBUG_LT_PRED(_Getcomp(), _Left, _Right);
    }

    template <class _Ty1, class _Ty2>
    bool _Compare(const _Ty1& _Left, const _Ty2& _Right) const { // compare _Ty1 to _Ty2, without debug checks
        return _Getcomp()(_Left, _Right);
    }

    template <class _Other>
    _Nodeptr _Lbound(const _Other& _Keyval) const { // find leftmost node not less than _Keyval
        _Nodeptr _Wherenode = _Get_data()._Myhead; // end() if search fails
        _Nodeptr _Pnode     = _Wherenode->_Parent;

        while (!_Pnode->_Isnil) {
            if (_Compare(_Key(_Pnode), _Keyval)) {
                _Pnode = _Pnode->_Right; // descend right subtree
            } else { // _Pnode not less than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode     = _Pnode->_Left; // descend left subtree
            }
        }

        return _Wherenode; // return best remembered candidate
    }

    template <class _Other>
    _Nodeptr _Ubound(const _Other& _Keyval) const { // find leftmost node greater than _Keyval
        auto& _My_data      = _Get_data();
        _Nodeptr _Pnode     = _My_data._Root();
        _Nodeptr _Wherenode = _My_data._Myhead; // end() if search fails

        while (!_Pnode->_Isnil) {
            if (_Compare(_Keyval, _Key(_Pnode))) { // _Pnode greater than _Keyval, remember it
                _Wherenode = _Pnode;
                _Pnode     = _Pnode->_Left; // descend left subtree
            } else {
                _Pnode = _Pnode->_Right; // descend right subtree
            }
        }

        return _Wherenode; // return best remembered candidate
    }

    const key_type& _Kfn(const value_type& _Val) const { // get key from value
        return _Traits::_Kfn(_Val);
    }

    const key_type& _Key(_Nodeptr _Pnode) const { // return reference to key in node
        return _Kfn(_Pnode->_Myval);
    }

#if _HAS_CXX17
public:
    using node_type = typename _Traits::node_type;

    node_type extract(const const_iterator _Where) { // extract the node denoted by _Where
        auto& _My_data = _Get_data();
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_My_data) && !_Where._Ptr->_Isnil,
            "map/set erase iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2

        const auto _Ptr = _My_data._Extract(_Where._Unwrapped());
        _My_data._Orphan_ptr(_Ptr);
        return node_type::_Make(_Ptr, _Getal());
    }

    node_type extract(const key_type& _Keyval) { // extract the first node whose key matches _Keyval
        const const_iterator _Where = find(_Keyval);
        if (_Where == end()) {
            return node_type{};
        }

        return extract(_Where);
    }

    auto insert(node_type&& _Handle) { // insert the node (if any) held in _Handle
        if (_Handle.empty()) {
            if constexpr (_Multi) {
                return end();
            } else {
                return _Insert_return_type<iterator, node_type>{end(), false, {}};
            }
        }

        _Check_node_allocator(_Handle);

        const auto _Result = _Insert_nohint(false, _Handle._Getptr()->_Myval, _STD addressof(_Handle));
        if constexpr (_Multi) {
            return iterator(_Result.first, _STD addressof(_Get_data()));
        } else {
            return _Insert_return_type<iterator, node_type>{
                iterator(_Result.first, _STD addressof(_Get_data())), _Result.second, _STD move(_Handle)};
        }
    }

    iterator insert(const const_iterator _Hint, node_type&& _Handle) {
        // insert the node held in _Handle (if any), with hint
        if (_Handle.empty()) {
            return end();
        }

        const auto _My_data_ptr = _STD addressof(_Get_data());
        _Check_node_allocator(_Handle);
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Hint._Getcont() == _My_data_ptr, "map/set insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        return iterator(
            _Insert_hint(_Hint._Unwrapped(), _Handle._Getptr()->_Myval, _STD addressof(_Handle)), _My_data_ptr);
    }

    template <class>
    friend class _Tree;

    template <class _Other_traits>
    void merge(_Tree<_Other_traits>& _That) { // transfer all nodes from _That into *this
        static_assert(is_same_v<_Nodeptr, typename _Tree<_Other_traits>::_Nodeptr>,
            "merge() requires an argument with a compatible node type.");

        static_assert(is_same_v<allocator_type, typename _Tree<_Other_traits>::allocator_type>,
            "merge() requires an argument with the same allocator type.");

        if constexpr (is_same_v<_Tree, _Tree<_Other_traits>>) {
            if (this == _STD addressof(_That)) {
                return;
            }
        }

#if _ITERATOR_DEBUG_LEVEL == 2
        if
            _CONSTEXPR_IF(!_Alnode_traits::is_always_equal::value) {
                _STL_VERIFY(_Getal() == _That._Getal(), "allocator incompatible for merge");
            }
#endif // _ITERATOR_DEBUG_LEVEL == 2

        _Node_merge_wrapper<_Other_traits> _Wrapper{_That, {}};
        auto _First      = _That.begin();
        const auto _Last = _That.end();
        while (_First != _Last) {
            _Wrapper._Where = _First;
            ++_First;
            const auto _Result = _Insert_nohint(false, *_Wrapper._Where, _STD addressof(_Wrapper));
            if (_Result.second) { // Reparent iterators for the merged node.
                _Reparent_ptr(_Wrapper._Where._Ptr, _That);
            }
        }
    }

    template <class _Other_traits>
    void merge(_Tree<_Other_traits>&& _That) { // transfer all nodes from _That into *this
        static_assert(is_same_v<_Nodeptr, typename _Tree<_Other_traits>::_Nodeptr>,
            "merge() requires an argument with a compatible node type.");

        static_assert(is_same_v<allocator_type, typename _Tree<_Other_traits>::allocator_type>,
            "merge() requires an argument with the same allocator type.");

        merge(_That);
    }

protected:
    _Nodeptr _Buy_if_not_node(node_type* const _Node_handle, _Any_tag) { // Extract node from node handle
        const auto _Ptr  = _Node_handle->_Release();
        const auto _Head = _Get_data()._Myhead;
        _Ptr->_Left      = _Head;
        _Ptr->_Right     = _Head;
        return _Ptr;
    }

    void _Destroy_if_node(node_type*) { // Handle retains ownership of node
    }

    template <class _Other_traits>
    struct _Node_merge_wrapper {
        _Tree<_Other_traits>& _That;
        typename _Tree<_Other_traits>::iterator _Where;
    };

    template <class _Other_traits>
    auto _Buy_if_not_node(_Node_merge_wrapper<_Other_traits>* const _Wrapper,
        _Any_tag) { // transition the denoted node into this container
        const auto _Ptr  = _Wrapper->_That._Get_data()._Extract(_Wrapper->_Where._Unwrapped());
        const auto _Head = _Get_data()._Myhead;
        _Ptr->_Left      = _Head;
        _Ptr->_Right     = _Head;
        return _Ptr;
    }

    template <class _Other_traits>
    void _Destroy_if_node(_Node_merge_wrapper<_Other_traits>*) { // source container retains ownership of node
    }

    template <class _Other_traits>
    void _Reparent_ptr(const _Nodeptr _Ptr, _Tree<_Other_traits>& _Old_parent) {
        // steal iterators with specified node pointer from _Old_parent
        (void) _Ptr;
        (void) _Old_parent;
#if _ITERATOR_DEBUG_LEVEL == 2
        _Lockit _Lock(_LOCK_DEBUG);
        auto& _Old_parent_data    = _Old_parent._Get_data();
        _Iterator_base12** _Pnext = &_Old_parent_data._Myproxy->_Myfirstiter;
        _STL_VERIFY(_Pnext, "source container corrupted");
        if (_Ptr == nullptr || _Ptr == _Old_parent_data._Myhead) {
            return;
        }

        const auto _My_saved_proxy               = _Get_data()._Myproxy;
        _Iterator_base12** const _My_saved_first = &_My_saved_proxy->_Myfirstiter;

        while (*_Pnext) {
            _Iterator_base12** const _Next = &(*_Pnext)->_Mynextiter;
            const auto _Iter               = static_cast<const_iterator*>(*_Pnext);
            if (_Iter->_Ptr == _Ptr) { // reparent the iterator
                *_Pnext            = *_Next;
                _Iter->_Myproxy    = _My_saved_proxy;
                _Iter->_Mynextiter = *_My_saved_first;
                *_My_saved_first   = _Iter;
            } else { // skip the iterator
                _Pnext = _Next;
            }
        }
#endif // _ITERATOR_DEBUG_LEVEL == 2
    }

    void _Check_node_allocator(node_type& _Handle) const { // ensure that _Handle and *this have compatible allocators
        (void) _Handle;
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(get_allocator() == _Handle._Getal(), "node handle allocator incompatible for insert");
#endif // _ITERATOR_DEBUG_LEVEL == 2
    }
#endif // _HAS_CXX17

    void _Alloc_sentinel_and_proxy() { // construct head node, proxy
        auto& _My_data  = _Get_data();
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alnode> _Proxy(_Alproxy, _My_data);
        _My_data._Myhead = _Node::_Buyheadnode(_Getal());
        _Proxy._Release();
    }

    template <class... _Valty>
    _Nodeptr _Buynode(_Valty&&... _Val) { // allocate a node with defaults and set links and value
        return _Node::_Buynode(_Getal(), _Get_data()._Myhead, _STD forward<_Valty>(_Val)...);
    }

    key_compare& _Getcomp() noexcept { // return reference to ordering predicate
        return _Mypair._Get_first();
    }

    const key_compare& _Getcomp() const noexcept { // return const reference to ordering predicate
        return _Mypair._Get_first();
    }

    _Alnode& _Getal() noexcept { // return reference to allocator
        return _Mypair._Myval2._Get_first();
    }

    const _Alnode& _Getal() const noexcept { // return const reference to allocator
        return _Mypair._Myval2._Get_first();
    }

    _Scary_val& _Get_data() noexcept { // return reference to _Scary_val
        return _Mypair._Myval2._Myval2;
    }

    const _Scary_val& _Get_data() const noexcept { // return const reference to _Scary_val
        return _Mypair._Myval2._Myval2;
    }

private:
    _Compressed_pair<key_compare, _Compressed_pair<_Alnode, _Scary_val>> _Mypair;
};

template <class _Traits>
_NODISCARD inline bool operator==(
    const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test for _Tree equality
    return _Left.size() == _Right.size()
           && _STD equal(_Left._Unchecked_begin(), _Left._Unchecked_end(), _Right._Unchecked_begin());
}

template <class _Traits>
_NODISCARD inline bool operator!=(
    const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test for _Tree inequality
    return !(_Left == _Right);
}

template <class _Traits>
_NODISCARD inline bool operator<(
    const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less < _Right for _Trees
    return _STD lexicographical_compare(
        _Left._Unchecked_begin(), _Left._Unchecked_end(), _Right._Unchecked_begin(), _Right._Unchecked_end());
}

template <class _Traits>
_NODISCARD inline bool operator>(
    const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less > _Right for _Trees
    return _Right < _Left;
}

template <class _Traits>
_NODISCARD inline bool operator<=(
    const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less <= _Right for _Trees
    return !(_Right < _Left);
}

template <class _Traits>
_NODISCARD inline bool operator>=(
    const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right) { // test if _Less >= _Right for _Trees
    return !(_Left < _Right);
}
_STD_END

#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // RC_INVOKED
#endif // _XTREE_

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
